/**
**************************************************************************************
*Founder Effect                                                                      *
*Copyright (C) 2006-2007, 5d Studios (www.5d-Studios.com)                            *
*                                                                                    *
*This library is free software; you can redistribute it and/or                       *
*modify it under the terms of the GNU Lesser General Public                          *
*License as published by the Free Software Foundation; either                        *
*version 2.1 of the License, or (at your option) any later version.                  *
*                                                                                    *
*This library is distributed in the hope that it will be useful,                     *
*but WITHOUT ANY WARRANTY; without even the implied warranty of                      *
*MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU                   *
*Lesser General Public License for more details.                                     *
*                                                                                    *
*You should have received a copy of the GNU Lesser General Public                    *
*License along with this library; if not, write to the Free Software                 *
*Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA      *
**************************************************************************************
*/
#pragma once

#include <vector>
#include <map>
#include "vector.h"
#include "geom.h"

#pragma warning( disable : 4244)

//- temp
#include "../render/IRender.h"

typedef unsigned int type_ID;
//----------
template<class T>
bool SwapAndErase( std::map< type_ID, T > &list, T &object )
{
    std::map< type_ID, T >::iterator it = list.find( object->GetID() );
    if ( it != list.end() )
    {
        list.erase( it );
        return true;
    }
    return false;
}

template<class T>
void AppendVector( std::map< type_ID, T > &list, std::map< type_ID, T > &appendMe )
{
    std::map< type_ID, T >::iterator it = appendMe.begin();
    for (; it != appendMe.end(); ++it )
    {
        list[ it->second->GetID() ] = it->second;
    }
}
//----------------

//----------
template<class T>
void AppendVector( std::vector< T > &list, std::map< type_ID, T >  &appendMe )
{
    std::map< type_ID, T >::iterator it = appendMe.begin();
    for (; it != appendMe.end(); ++it )
    {
        list.push_back( it->second );
    }
}

//template<class T>
//bool SwapAndErase( std::vector< T > &list, T &object )
//{
//    std::vector< T >::iterator it = list.begin();
//    for(; it != list.end(); ++it )
//    {
//        if ( (*it) == object )//(*it)->GetID() == object->GetID() )
//        {
//            list.erase( it );
//            return true;
//        }
//    }
//    return false;
//}
//
//template<class T>
//void AppendVector( std::vector< T > &list, std::vector< T > &appendMe )
//{
//    for ( size_t i = 0; i < appendMe.size(); ++i )
//    {
//        list.push_back( appendMe[i] );
//    }
//}

/**
================================================================================
QuadTree Node
================================================================================
*/
template <class T>
class QuadTreeNode
{
public:
    QuadTreeNode(Rect r)
    {
        for ( int i = 0; i < MAX_CHILDREN;  ++i )
            m_children[i] = NULL;
        
        m_bounds.Set( r.x, r.y, r.width, r.height);
    }

    /** Put an item in the QuadTree */
    virtual bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            bool inChild = false;
            for ( int i=0;i<MAX_CHILDREN; ++i)
            {
                if ( m_children[i]->GetBounds().Intersects( objectBounds ) ) 
                {
                    if ( m_children[i]->Put( object ) )
                        inChild = true;
                }
            }
            return inChild;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    virtual bool Pop( T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            bool inChild = false;
            for ( int i=0;i<MAX_CHILDREN; ++i)
            {
                if ( m_children[i]->GetBounds().Intersects( objectBounds ) ) 
                {
                    if ( m_children[i]->Pop( object ) )
                        inChild = true;
                }
            }
            return inChild;
        }
        return false;
    }

    /** Get all the objects contained in this region */
    virtual void GetObjects( const Rect &region, std::vector< T > &list )
    {
        if ( m_bounds.Intersects( region ) )
        {
            bool NW = m_children[0]->IsInBounds( region );
            bool NE = m_children[1]->IsInBounds( region );
            bool SW = m_children[2]->IsInBounds( region );
            bool SE = m_children[3]->IsInBounds( region );
          
            if ( NW )
                m_children[0]->GetObjects( region, list ) ;
            if ( NE )
                m_children[1]->GetObjects( region, list ) ;
            if ( SW )
                m_children[2]->GetObjects( region, list ) ;
            if ( SE )
                m_children[3]->GetObjects( region, list ) ;
        }
    }
    /** Get all the objects contained hit by the line*/
    virtual void GetObjects( const Vector2f &p1, const Vector2f &p2, std::vector< T > &list )
    {
        if ( m_bounds.LineIntersects( p1, p2 ) )
        {
            bool NW = m_children[0]->LineIntersects( p1, p2 );
            bool NE = m_children[1]->LineIntersects( p1, p2 );
            bool SW = m_children[2]->LineIntersects( p1, p2 );
            bool SE = m_children[3]->LineIntersects( p1, p2 );

            if ( NW )
                m_children[0]->GetObjects( p1, p2, list ) ;
            if ( NE )
                m_children[1]->GetObjects( p1, p2, list ) ;
            if ( SW )
                m_children[2]->GetObjects( p1, p2, list ) ;
            if ( SE )
                m_children[3]->GetObjects( p1, p2, list ) ;
        }
    }
    /** Get all the objects contained in this region */
    virtual void GetObjects( const Rect &region, std::map< type_ID, T > &list )
    {
        if ( m_bounds.Intersects( region ) )
        {
            bool NW = m_children[0]->IsInBounds( region );
            bool NE = m_children[1]->IsInBounds( region );
            bool SW = m_children[2]->IsInBounds( region );
            bool SE = m_children[3]->IsInBounds( region );
          
            if ( NW )
                m_children[0]->GetObjects( region, list ) ;
            if ( NE )
                m_children[1]->GetObjects( region, list ) ;
            if ( SW )
                m_children[2]->GetObjects( region, list ) ;
            if ( SE )
                m_children[3]->GetObjects( region, list ) ;
        }
    }
    /** Get all the objects contained hit by the line*/
    virtual void GetObjects( const Vector2f &p1, const Vector2f &p2, std::map< type_ID, T > &list )
    {
        if ( m_bounds.LineIntersects( p1, p2 ) )
        {
            bool NW = m_children[0]->LineIntersects( p1, p2 );
            bool NE = m_children[1]->LineIntersects( p1, p2 );
            bool SW = m_children[2]->LineIntersects( p1, p2 );
            bool SE = m_children[3]->LineIntersects( p1, p2 );

            if ( NW )
                m_children[0]->GetObjects( p1, p2, list ) ;
            if ( NE )
                m_children[1]->GetObjects( p1, p2, list ) ;
            if ( SW )
                m_children[2]->GetObjects( p1, p2, list ) ;
            if ( SE )
                m_children[3]->GetObjects( p1, p2, list ) ;
        }
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_bounds.Intersects( region ); };
    /** Check to see if the line intersects this nodes bounds */
    bool    LineIntersects( const Vector2f &p1, const Vector2f &p2 ) { return m_bounds.LineIntersects( p1, p2 ); };


    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_bounds; };

    /** Clear all the contents */
    virtual void Clear() {
        for(int i = 0; i < MAX_CHILDREN; ++i )
        {
            m_children[i]->Clear();
        }
    };
    /** Number of objects */
    virtual size_t Size() {
        size_t j = 0;
        for ( size_t i=0;i<MAX_CHILDREN; ++i )
        {
            j += m_children[i]->Size();
        }
        return j;
    }

    static enum {
        NORTHWEST = 0,
        NORTHEAST = 1,
        SOUTHWEST = 2,
        SOUTHEAST = 3,

        MAX_CHILDREN
    };
    
    // children
    QuadTreeNode*    m_children[MAX_CHILDREN];
        // this nodes bounds 
    Rect    m_bounds;

    virtual void Draw(IRender *r, ICamera *cam)
    {   r->SetColor( 0,0,1,1);
        r->DrawRect( m_bounds.x - cam->GetPosition().x, m_bounds.y - cam->GetPosition().y, m_bounds.width, m_bounds.height );
        for (int i=0;i<MAX_CHILDREN; ++i )
            m_children[i]->Draw(r, cam);
    }
protected:




public:
    virtual ~QuadTreeNode(void)
    {
        for ( int i = 0; i < MAX_CHILDREN;  ++i )
            if ( m_children[i] ) delete m_children[i];
          
    };
};



/**
================================================================================
LeafNode
================================================================================
*/
template <class T>
class QuadTreeLeaf : public QuadTreeNode<T>
{
public:
    QuadTreeLeaf(Rect r) : QuadTreeNode(r) {};

    /** Put an item in the QuadTree */
    bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            m_objects[ object->GetID() ] = object;
            return true;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    bool Pop( T& object )
    {
        return SwapAndErase( m_objects, object );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, std::vector< T > &list )
    {
        return AppendVector( list, m_objects );
    }
    /** Get all the objects contained hit by the line*/
    void GetObjects( const Vector2f &p1, const Vector2f &p2, std::vector< T > &list )
    {
        return AppendVector( list, m_objects );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, std::map< type_ID, T > &list )
    {
        return AppendVector( list, m_objects );
    }
    /** Get all the objects contained hit by the line*/
    void GetObjects( const Vector2f &p1, const Vector2f &p2, std::map< type_ID, T > &list )
    {
        return AppendVector( list, m_objects );
    }

    /** Clear all the contents */
    void Clear() {
        m_objects.clear();
    };
    size_t Size() { return m_objects.size(); };

   void Draw(IRender *r, ICamera *cam)
    {   r->SetColor( 1,1,1,0.4f);
        r->DrawRect( m_bounds.x - cam->GetPosition().x, m_bounds.y - cam->GetPosition().y, m_bounds.width, m_bounds.height );
        if ( !m_objects.empty() ) {
            r->SetColor(1,1,1);
            r->DrawString( m_bounds.x - cam->GetPosition().x + 10, m_bounds.y - cam->GetPosition().y + 10, "%d", m_objects.size() );
            //r->DrawString( m_bounds.x - cam->GetPosition().x + 30, m_bounds.y - cam->GetPosition().y + 10, (m_objects.begin()->second->GetName()).c_str() );
            r->DrawString( m_bounds.x - cam->GetPosition().x + 10, m_bounds.y - cam->GetPosition().y + 30, "%d %d", m_bounds.x, m_bounds.y );
            r->SetColor( 0.4f, 0.6f, 0.8f, 0.4f );
            r->FillRect( m_bounds.x - cam->GetPosition().x, m_bounds.y - cam->GetPosition().y, m_bounds.width, m_bounds.height );
        }

    }
private:
    // list of objects in this node
    typedef std::map< type_ID, T >/*std::vector< T >*/ type_List;
    type_List m_objects;
public:
    virtual ~QuadTreeLeaf(void) {};
};






/**
================================================================================
Data Structure for holding
world data
================================================================================
*/
template <class T>
class QuadTree
{
public:
    QuadTree(float minw, float minh, float maxw, float maxh):  m_maxWidth(maxw), 
                                                            m_maxHeight(maxw),
                                                            m_minWidth(minw),
                                                            m_minHeight(minh)
    {
        m_root = new QuadTreeNode<T>( Rect( 0, 0, m_maxWidth, m_maxHeight ) );
        BuildTree( m_root );
    }
    QuadTree();

    /** Put an item in the QuadTree */
    bool Put( T& object )
    {
        return m_root->Put( object );
    }
    /** Pop off an object */
    bool Pop( T& object )
    {
        return m_root->Pop( object );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, std::vector< T > &list )
    {
        return m_root->GetObjects( region, list );
    }
    /** Get all the objects that intersect the line */
    void GetObjects( const Vector2f &p1, const Vector2f &p2, std::vector< T > &list )
    {
        return m_root->GetObjects( p1, p2, list );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, std::map< type_ID, T >  &list)
    {
        return m_root->GetObjects( region, list );
    }
    /** Get all the objects that intersect the line */
    void GetObjects( const Vector2f &p1, const Vector2f &p2, std::map< type_ID, T > &list )
    {
        return m_root->GetObjects( p1, p2, list );
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_root->IsInBounds(region); };

    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_root->m_bounds; };

    /** Clear all the contents */
    void Clear() {
        m_root->Clear();
    };
    /** Get the number of elements in the tree */
    size_t Size() { return m_root->Size(); };

    // TEMP
    void Draw(IRender *r, ICamera *cam) {
        m_root->Draw(r, cam);
    }
private:
    /** BuildTree */
    template<class T>
    void BuildTree( QuadTreeNode<T>* root ) 
    {
        float h_width  = root->m_bounds.width / 2;
        float h_height = root->m_bounds.height / 2;

        
        if (  h_width < m_minWidth*2 && h_height < m_minHeight*2 ) 
        // build the leafs
        {
            Rect b = root->GetBounds();
            root->m_children[ root->NORTHWEST ] = new QuadTreeLeaf<T>( Rect(b.x, b.y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeLeaf<T>( Rect(b.x+h_width, b.y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeLeaf<T>( Rect(b.x, b.y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeLeaf<T>( Rect(b.x+h_width, b.y+h_height, h_width, h_height ) );
        }
        else    // build the branches
        {   Rect b = root->GetBounds();
            root->m_children[ root->NORTHWEST ] = new QuadTreeNode<T>( Rect(b.x, b.y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeNode<T>( Rect(b.x+h_width, b.y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeNode<T>( Rect(b.x, b.y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeNode<T>( Rect(b.x+h_width, b.y+h_height, h_width, h_height ) );

            BuildTree ( root->m_children[ root->NORTHWEST ] );
            BuildTree ( root->m_children[ root->NORTHEAST ] );
            BuildTree ( root->m_children[ root->SOUTHWEST ] );
            BuildTree ( root->m_children[ root->SOUTHEAST ] );
        }
    }

    //  max size
    float   m_maxWidth,
            m_maxHeight;

    //  min size
    float   m_minWidth,
            m_minHeight;

    // root
    QuadTreeNode<T>*   m_root;

public:
    virtual ~QuadTree(void) { delete m_root; };
};

